package com.zh.lex;

import java.util.*;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.stream.Collectors;
import static com.zh.lex.ReTran.strTrans;

public class RE2NFA {

    public static final char NullChar = 'ε'; // 空串
    public static final char TranChar = '\\'; // 转义字符 \

    public RE2NFA(String str) {
        addEndStat(str);
        handle();
    }

    public RE2NFA() {};
    public TreeMap<Long, Set<Integer>> getStatJump() {
        return statTable;
    }

    public RE2NFA handle() {
        _handleA();
        _handleMeaningless();
        _handleB();
        return this;
    }

    private void _handleB() {
        Set<Long> sl = new HashSet<>(statTable.size());
        for (Long l : statTable.subMap(0L, true, int2long(0, 1), false).keySet()) {
            _handleC(sl, l);
        }
        statTable.entrySet().forEach(e -> {
            Long k = e.getKey();
            if (sl.contains(k))
                return;
            Set<Integer> v = e.getValue();
            Set<Integer> ts = new HashSet<>();
            for (Integer i : v) {
                Set<Integer> t = statTable.get(int2long(i, 0));
                if (null != t)
                    ts.addAll(t);
            }
            v.addAll(ts);
        });

        Set<Integer> si = statTable.get(int2long(startStat, "" + NullChar));
        if (null != si)
            for (int i : si) {
                tm.subMap(int2long(0, i), true, int2long(0, i + 1), false).forEach((k, v) -> {
                    if (!statTable.containsKey(v))
                        return;
                    int re = long2Re(v);
                    statTable.put(int2long(startStat, re), new HashSet<>(statTable.get(v)));
                });
                if (endStat.contains(i))
                    endStat.add(startStat);
             }

        statTable.subMap(0L, true, int2long(0, 1), false).clear();

    }

    private void _handleC(Set<Long> sl, Long l) {
        if (sl.contains(l))
            return;
        sl.add(l);
        Set<Integer> si = statTable.get(l);
        if (null == si || si.size() == 0)
            return;
        Set<Integer> ts = new HashSet<>();
        for (Integer i : si) {
            _handleC(sl, int2long(i, 0));
            Set<Integer> t = statTable.get(int2long(i, 0));
            if (null != t)
                ts.addAll(t);
        }
        si.addAll(ts);
    }

    /**
     * 起始状态
     */
    private int startStat = 1;
    /**
     * 结束状态
     */
    private Set<Integer> endStat = new HashSet<>();

    public int getStartStat() {
        return startStat;
    }

    public Set<Integer> getEndStat() {
        return endStat;
    }

    private TreeMap<Long, Long> tm = new TreeMap();
    /**
     * 处理无意义的跳转
     */
    private void _handleMeaningless() {
        tm = statTable.keySet().stream().collect(Collectors.toMap(k -> {
            int s = long2Stat(k);
            int r = long2Re(k);
            return int2long(r, s);
        }, v -> v, (v1, v2) -> v1, TreeMap::new));

        Map<Integer, Integer> changeStat = new HashMap<>();
        Iterator<Map.Entry<Long, Set<Integer>>> it =  statTable.subMap(0L, true, 1L << 32, false).entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry<Long, Set<Integer>> e = it.next();
            Long k = e.getKey();

            int s = long2Stat(k);
            int r = long2Re(k);
            long k1 = int2long(r, s);

            Set<Integer> si = e.getValue();
            // 移除 null 跳回自己
            si.remove(s);
            if (si.size() == 0)
                it.remove();
            if (si.size() != 1)
                continue;

            Integer i = si.stream().findAny().get();

            Map.Entry<Long, Long> me = tm.higherEntry(k1);
            if (null == me) {
                changeStat.put(s, i);
                it.remove();
                continue;
            }

            if (long2Re(me.getKey()) == s)
                continue;

            changeStat.put(s, i);
            it.remove();
        }
        delMeaningless(changeStat);

//        {
//            Map<Integer, Integer> si = new HashMap<>();
//            Set<Integer> t = new HashSet<>();
//            statTable.subMap(0L, true, 1L << 32, false).entrySet().forEach(e -> {
//                Long k = e.getKey();
//                Set<Integer> v = e.getValue();
//                for (Integer i : v) {
//                    if (si.containsKey(i))
//                        t.add(i);
//                    else si.put(i, long2Stat(k));
//                }
//            });
//            for (int i : t)
//                si.remove(i);
//
//            if (si.size() > 0)
//            statTable.subMap(1L << 32, true, Long.MAX_VALUE, false).entrySet().forEach(e -> {
//                if (si.size() == 0)
//                    return;
//                Set<Integer> ss = e.getValue();
//                for (Integer i : ss)
//                    si.remove(i);
//            });
//            startStat = si.getOrDefault(startStat, startStat);
//            endStat = si.getOrDefault(endStat, endStat);
//            si.entrySet().forEach(e -> {
//                Integer k = e.getKey();
//                final Integer v = e.getValue();
//                Set<Integer> ssss = statTable.get(int2long(v, 0));
//                ssss.remove(k);
//                if (ssss.size() == 0)
//                    statTable.remove(int2long(v, 0));
//                Iterator<Map.Entry<Long, Set<Integer>>> it1 = statTable.subMap(int2long(k, 0), true, int2long(k, Integer.MAX_VALUE), true).entrySet().iterator();
//                while (it.hasNext()) {
//                    Map.Entry<Long, Set<Integer>> e1 = it.next();
//                    Long k1 = e1.getKey();
//                    Set<Integer> v1 = e1.getValue();
//                    int re = long2Re(k1);
//                    Long index = int2long(v, re);
//                    if (!statTable.containsKey(index))
//                        statTable.put(index, v1);
//                    else statTable.get(index).addAll(v1);
//                    it.remove();
//                }
//            });
//        }
    }

    private Map<Integer, Integer> changeStat = new HashMap<>();

    public Map<Integer, Integer> getChangeStat() {
        return changeStat;
    }

    /**
     * 删除无意义的跳转
     * @param changeStat
     */
    private void delMeaningless(Map<Integer, Integer> changeStat) {
        initChangeStat(changeStat);
        this.changeStat = changeStat;
        startStat = changeStat.getOrDefault(startStat, startStat);
        change(endStat);

        statTable.entrySet().forEach(e -> {
            Set<Integer> v = e.getValue();
            change(v);
        });
    }

    private void change(Set<Integer> v) {
        Iterator<Integer> it = v.iterator();
        Set<Integer> ts = new HashSet<>(v.size());
        while (it.hasNext()) {
            Integer i = it.next();
            if (!changeStat.containsKey(i))
                continue;
            it.remove();
            ts.add(changeStat.get(i));
        }
        v.addAll(ts);
    }

    /**
     * 处理替换关系 如 A 可替换成 B 可替换成 C
     * 实际上 需要 A 与 C 建立映射即可
     * @param changeStat
     */
    private void initChangeStat(Map<Integer, Integer> changeStat) {
        for (int i : changeStat.keySet())
            _getNewestStat(changeStat, i);
    }

    /**
     * 归并集处理替换关系
     * @param changeStat
     * @param i
     * @return
     */
    private int _getNewestStat(Map<Integer, Integer> changeStat, int i) {
        if (!changeStat.containsKey(i))
            return i;
        int t = _getNewestStat(changeStat, changeStat.get(i));

        changeStat.put(i, t);
        return t;
    }

    public static void main(String[] args) {
		int i = 6;
		while (i-- > 0)
			System.out.println(i);
	}
    
    /**
     * 正则表达式处理
     */
    private void _handleA() {
        while (queue.size() > 0) {
            String str = queue.poll();
            long l = int2long(23, str);

            if ('*' == str.charAt(str.length() -1)) {
            	// 最后一可能是 \*
            	
            	int i = str.length() - 1;
            	int c = 0;
            	char[] cs = str.toCharArray();
            	while (i-- > 0) {
            		if ('\\' == cs[i])
            			c++;
            		else break;
            	}
            	if (0 == (c & 1)) {
	                _handleClosure(str);
	                continue;
            	}
            }
            StringBuffer sb = findMinRe(str.toCharArray(), 0);
            if (sb.length() == str.length()) {
                _handleParenthesis(str);
                continue;
            }
            _handleOr(str, sb.toString());
        }
    }


    /**
     * 处理正则表达式中的括号 ()
     * @param re
     */
    private void _handleParenthesis(String re) {
        boolean flag = re.length() == 2;

        // ()
        Map<Long, Set<Integer>> m = new HashMap<>(statTable.subMap(int2long(0, re), true, int2long(Integer.MAX_VALUE, re), true));

        String creStr = re.substring(0, re.length() - 1);
        for (Long lo : m.keySet()) {
            int i = long2Stat(lo);
            Set<Integer> j = m.get(lo);
            clearNextStat(lo);
            if (flag) {
                // () 里什么都没有
                addStatJump(i, null, j);
                continue;
            }
            int cen = nextStat();
            initHandle(re.substring(1, re.length() - 1).toCharArray(), 0, i, cen);
            addStatJump(cen, null, j);
        }
        popStringIndex(re);
    }

    /**
     * 处理正则表达式中的 |
     * @param re
     * @param s
     */
    private void _handleOr(String re, String s) {
        // |
        final String r = re;
        final String s1 = s;

        Map<Long, Set<Integer>> m = new HashMap<>(statTable.subMap(int2long(0, re), true, int2long(Integer.MAX_VALUE, re), true));
        for (Long lo : m.keySet()) {
            Set<Integer> j = m.get(lo);
            int i = long2Stat(lo);
            re = r;
            s = s1;
            while(true) {
                addStatJump(i, s.toString(), j);
                if (re.length() <= s.length())
                    break;
                re = re.substring(s.length()+ 1);
                s = findMinRe(re.toCharArray(), 0).toString();
            }
            clearNextStat(lo);
        }

        popStringIndex(r);
    }

    /**
     * 处理正则表达式中的闭包 *
     * @param re
     */
    private void _handleClosure(String re) {
        // *
//        int index = map.get(re);
//        int len = this.statIndex;
        String creStr = re.substring(0, re.length() - 1);

        Map<Long, Set<Integer>> m = new HashMap<>(statTable.subMap(int2long(0, re), true, int2long(Integer.MAX_VALUE, re), true));
        for (Long lo : m.keySet()) {
            Set<Integer> j = m.get(lo);
            int i = long2Stat(lo);
            int cen = nextStat();
            addStatJump(i, null, cen);
            addStatJump(cen, creStr, cen);
            addStatJump(cen, null, j);
            clearNextStat(lo);
        }

        popStringIndex(re);

    }

    /**
     * re 对应的Integer
     */
    private final HashMap<String, Integer> map = new HashMap<>(32);

    public Map<String, Integer> getMap() {
        return map;
    }

    /**
     * 简单处理，将直接拼接拆分
     */
    private void initHandle(char[] re, int i, int leftStat, int rightStat) {
        if (isEnd(re, i))
            return;
        final int len = re.length;
        StringBuffer s = findMinRe(re, i);
        i = i + s.length() - 1;
        if (len == i + 1) {
            addStatJump(leftStat, s.toString(), rightStat);
            return;
        }
        char n = re[i + 1];
        if ('*' == n) {
            i++;
            s.append('*');

            int cent = rightStat;
            if ((i + 1) != re.length)
                cent = nextStat();
            addStatJump(leftStat, s.toString(), cent);
            initHandle(re, i + 1, cent, rightStat);
            return;
        }
        while ('|' == n) {
            i++;
            s.append('|');
            StringBuffer sb = findMinRe(re, i + 1);
            s.append(sb);
            i = i + sb.length();
            if (len == i + 1) {
                addStatJump(leftStat, s.toString(), rightStat);
                return;
            }
            n = re[i + 1];
        }
        if (len == i + 1) {
            addStatJump(leftStat, s.toString(), rightStat);
            return;
        }
        int cent = nextStat();
        addStatJump(leftStat, s.toString(), cent);
        initHandle(re, i + 1, cent, rightStat);

    }

    /**
     *
     * @param re 需要查找的表达式
     * @param index 从 index 处开始查找
     * @return 查找符合的最小正则表达式
     */
    private StringBuffer findMinRe(char[] re, int index) {
        StringBuffer sb = new StringBuffer();
        int leftPart = 0;
        boolean tranFlag = false; // 上个字符是否为转义字符
        for (int i = index; i < re.length; i++) {
            char c = re[i];

            if (!tranFlag) {
                if (c == '(') {
                    leftPart++;
                    sb.append(c);
                    continue;
                }
                if (c == ')') {
                    if (leftPart <= 0)
                        throw new IllegalArgumentException();
                    leftPart--;
                    sb.append(c);
                    if (leftPart == 0)
                        return sb;
                    continue;
                }
                if (TranChar == c) {
                    tranFlag = true;
                    sb.append(c);
                    continue;
                }
            } else {
                tranFlag = false;
            }
            if (leftPart > 0) {
                sb.append(c);
                continue;
            }
            if (tranFlag && (c == '|' || c == '*')) {
                throw new IllegalArgumentException();
            }
            return sb.append(c);
        }
        throw new IllegalArgumentException();
    }

    /**
     * 输出正则表达式的跳转
     */
    public void displayStatTable() {
        System.out.println("start : " + startStat + "\tendStat : " + endStat);
        Map<Integer, String> m = new HashMap<>(map.size() << 1);
        for (String s : map.keySet()) {
            if (null == s)
                continue;
            m.put(map.get(s), s);
        }

        for (Long k : statTable.keySet()) {
            int thisStat = long2Stat(k);
            int re = long2Re(k);
            System.out.println(thisStat + "\t" + displayStr(m.get(re)) + "\t = \t" + statTable.get(k));
        }
    }

    static String displayStr(String str) {
        if (null == str || str.length() == 1)
            return str;
        StringBuffer sb = new StringBuffer(str.length());
        boolean flag = false;
        for (char c : str.toCharArray()) {
            if (flag) {
                sb.append(c);
                flag = false;
                continue;
            }
            if (TranChar == c) {
                flag = true;
                continue;
            }
            sb.append(c);
        }
        return sb.toString();
    }

    /**
     * 输出 markdown 语法
     * 可使用 有道云笔
     */
    public void displayGraph() {
        Map<Integer, String> m = new HashMap<>(map.size() << 1);
        for (String s : map.keySet()) {
            if (null == s)
                continue;
            m.put(map.get(s), s);
        }
        for (Long k : statTable.keySet()) {
            int thisStat = long2Stat(k);
            int re = long2Re(k);
            Set<Integer> si = statTable.get(k);
            for (int i : si)
                System.out.println(thisStat + "-->|\"" + displayStr(m.get(re)) + "\"|" + i);
        }
    }

    /**
     * 使用该网站可视化状态转移图 <br>
     * http://magjac.com/graphviz-visual-editor/
     */
    public void disGraphviz() {
        Map<Integer, String> m = new HashMap<>(map.size() << 1);
        for (String s : map.keySet()) {
            if (null == s)
                continue;
            m.put(map.get(s), s);
        }
        System.out.println("digraph G {");

        System.out.println("{");
        for (int e : endStat)
            System.out.println(e + " [shape=doublecircle]");
        System.out.println("}");
        for (Long k : statTable.keySet()) {
            int thisStat = long2Stat(k);
            int re = long2Re(k);
            Set<Integer> si = statTable.get(k);
            StringBuffer ssss = new StringBuffer(si.size() << 1);
            ssss.append("{");
            for (Integer i : si)
                ssss.append(i + " ");
            ssss.append("}");
            System.out.println(thisStat + "->" + ssss + " [label=\"" + displayStr(m.get(re)) + "\"]");
        }
        System.out.println("}");
    }

    /**
     * 存储跳转关联关系 <br>
     * key 分为高位和低位 <br>
     * 高位表示遇到的字符 <br>
     * 低位表示当前状态
     */
    private final TreeMap<Long, Set<Integer>> statTable = new TreeMap<>();

    /**
     * 移除跳转
     * @param l
     */
    private void clearNextStat(long l) {
        statTable.remove(l);
    }

    /**
     *
     * @param thisStat 当前状态
     * @param re 正则表达式
     * @return 转换后的 key
     */
    public long int2long(int thisStat, String re) {
        return int2long(thisStat, map.get(re));
    }

    /**
     *
     * @param thisStat 当前状态
     * @param re 正则表达式
     * @return 转换后的 key
     */
    public static long int2long(int thisStat, int re) {
        return (Long.valueOf(re) << 32) | thisStat;
    }

    /**
     * key 转 re 对应的 int
     * @param l
     * @return
     */
    public static int long2Re(long l) {
        return (int) (l >>> 32);
    }

    /**
     * key 转 状态
     * @param l
     * @return
     */
    public static int long2Stat(long l) {
        return (int)(l & 0xFFFFFFFF);
    }

    private final Queue<String> queue = new ConcurrentLinkedQueue<>();

    private void addQueue(String str) {
        if (null != str && str.length() > 1 && !map.containsKey(str)) {
            if (str.length() == 2 && str.startsWith("\\")){}
            else
                queue.add(str);
        }
    }

    private void addStatJump(int thisStat, String str, Set<Integer> nextStat) {
        if (strTrans.containsKey(str)) {
            str = strTrans.get(str);
        }

        addQueue(str);
        int index = nextStringIndex(str);
        Long l = int2long(thisStat, index);
        if (!statTable.containsKey(l)) {
            statTable.put(l, new HashSet<>(nextStat));
        } else statTable.get(l).addAll(nextStat);
    }

//    private static final Map<String, String> strTrans = new HashMap<>();
//
//    static {
//        if (escape) {
//            strTrans.put("\\d", "(9|0)");
//        }
//    }

    private void addStatJump(int thisStat, String str, Integer... nextStat) {
        addStatJump(thisStat, str, new HashSet<>(Arrays.asList(nextStat)));
    }

    public int addEndStat(String str) {
        int next = nextStat();
        addStatJump(startStat, "(" + str + ")", next);
        endStat.add(next);
        return next;
    }

    private Set<Integer> getStatJum(int thisStat, String str) {
        int index = map.get(str);
        Long l = (Long.valueOf(index) << 32) | thisStat;
        return statTable.get(l);
    }

    private boolean isEnd(char[] re, int i) {
        return null == re || re.length == 0 || re.length <= i;
    }

    private final List<Integer> li = new ArrayList<>(32);
    private int nextStringIndex(String str) {
        if (map.containsKey(str))
            return map.get(str);
        if (li.size() == 0)
            map.put(str, map.size());
        else map.put(str, li.remove(0));
        return map.get(str);
    }

    private void popStringIndex(String str) {
        if (str.equals("" + NullChar))
            return;
        li.add(map.remove(str));
    }

    private int statIndex = 2;
    int nextStat() {
        return statIndex++;
    }

    {
        map.put(null, 0);
        map.put(NullChar+"", 0);
    }

}
